package cc.ccoke.algorithms.primary.chapter02;

import cc.ccoke.algorithms.util.ArrayUtils;

import java.util.Scanner;


/**
 * 用荷兰国旗改进的随机快速排序
 * @author ccoke
 */
public class QuickSort {

    public static void sort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int p = left - 1;
        int q = right + 1;
        // 随机获取一个参考数
        int num = arr[(int)(Math.random() * (right - left + 1)) + left];
        int index = left;
        while (index < q) {
            if (arr[index] < num) {
                ArrayUtils.swap(arr, ++p, index ++);
            } else if (arr[index] > num) {
                ArrayUtils.swap(arr, --q, index);
            } else {
                index ++;
            }
        }
        ArrayUtils.print(arr);
        sort(arr, left, p);
        sort(arr, q, right);
    }


    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateByInt(10, 20);
        System.out.println("--- before ---");
        ArrayUtils.print(arr);
        System.out.println("--- after ---");
        sort(arr, 0, arr.length -1);
        ArrayUtils.print(arr);
    }

}
